CAP 是什么
CAP 理论，被戏称为【帽子理论】。CAP 理论由 Eric Brewer 在 ACM 研讨会上提出，而后 CAP 被奉为分布式领域的重要理论 [1]。
分布式系统的 CAP 理论：首先把分布式系统中的三个特性进行了如下归纳：
一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）
可用性（A）：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）
分区容忍性（P）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在 C 和 A 之间做出选择。（分区状态可以理解为部分机器不连通了，比如机器挂了，繁忙失去响应，单机房故障等）
Partition 字面意思是网络分区，即因网络因素将系统分隔为多个单独的部分，有人可能会说，网络分区的情况发生概率非常小啊，是不是不用考虑 P，保证 CA 就好。要理解 P，我们看回 CAP 证明中 P 的定义：
In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.
网络分区的情况符合该定义，网络丢包的情况也符合以上定义，另外节点宕机，其他节点发往宕机节点的包也将丢失，这种情况同样符合定义。现实情况下我们面对的是一个不可靠的网络、有一定概率宕机的设备，这两个因素都会导致 Partition，因而分布式系统实现中 P 是一个必须项，而不是可选项。
高可用、数据一致性是很多系统设计的目标，但是分区又是不可避免的事情。我们来看一看分别拥有 CA、CP 和 AP 的情况。
CA without P：如果不要求 P（不允许分区），则 C（强一致性）和 A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，CA 系统基本上是单机系统，比如单机数据库。2PC 是实现强一致性的具体手段。
from http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf
CP without A：如果不要求 A（可用），相当于每个请求都需要在 Server 之间强一致，而 P（分区）会导致同步时间无限延长，如此 CP 也是可以保证的。很多传统的数据库分布式事务都属于这种模式。
from http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf
AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的 NoSQL 都属于此类。
from http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf
CAP 理论的证明
该理论由 Brewer 提出，2 年后就是 2002 年，Lynch 与其他人证明了 Brewer 猜想，从而把 CAP 上升为一个定理。但是，它只是证明了 CAP 三者不可能同时满足，并没有证明任意二者都可满足的问题，所以，该证明被认为是一个收窄的结果。
Lynch 的证明相对比较简单：采用反证法，如果三者可同时满足，则因为允许 P 的存在，一定存在 Server 之间的丢包，如此则不能保证 C，证明简洁而严谨。
在该证明中，对 CAP 的定义进行了更明确的声明：
C：一致性被称为原子对象，任何的读写都应该看起来是“原子“的，或串行的。写后面的读一定能读到前面写的内容。所有的读写请求都好像被全局排序一样。
A：对任何非失败节点都应该在有限时间内给出请求的回应。（请求的可终止性）
P：允许节点之间丢失任意多的消息，当网络分区发生时，节点之间的消息可能会完全丢失。
对于 CAP 进一步的案例解释
2010 年的这篇文章《brewers-cap-theorem-on-distributed-systems》[2] ，用了三个例子来阐述CAP:
example1：单点的mysql；
example2：两个mysql，但不同的mysql存储不同的数据子集,相当于sharding；
example3：两个mysql，对A的一个insert操作，需要在B上执行成功才认为操作完成（类似复制集）。
作者认为在 example1 和 example2 上都能保证强一致性，但不能保证可用性；在 example3 这个例子，由于分区（partition）的存在，就需要在一致性与可用性之间权衡。对于复制而言，在很多场景下不追求强一致性。比如用户支付之后，交易记录落地了；但可能消费记录的消息同步存在延迟，比如消息阻塞了。在金融业务中，采取类似两地三中心架构，往往可能采取本地数据和异地机房数据同时写成功再返回的方式。这样付出了性能的损耗，响应时间变长。但发生机房故障后，能确保数据是完全可以读写的，保障了一致性。
CAP 理论澄清
【CAP理论十二年回顾："规则"变了】一文首发于 Computer 杂志，后由InfoQ和IEEE联合呈现,非常精彩[3]，文章表达了几个观点。
“三选二”是一个伪命题
不是为了 P （分区容忍性），要在 A 和 C 之间选择一个。分区很少出现，CAP 在大多数时候允许完美的 C 和 A 。但当分区存在或可感知其影响的情况下，就要预备一种策略去探知分区并显式处理其影响。这样的策略应分为三个步骤：探知分区发生，进入显式的分区模式以限制某些操作，启动恢复过程以恢复数据一致性并补偿分区期间发生的错误。
“一致性的作用范围”其实反映了这样一种观念，即在一定的边界内状态是一致的，但超出了边界就无从谈起。比如在一个主分区内可以保证完备的一致性和可用性，而在分区外服务是不可用的。Paxos 算法和原子性多播（atomic multicast）系统一般符合这样的场景。像 Google 的一般做法是将主分区归属在单个数据中心里面，然后交给 Paxos 算法去解决跨区域的问题，一方面保证全局协商一致（global consensus）如 Chubby，一方面实现高可用的持久性存储如 Megastore。
ACID、BASE、CAP
ACID 和 BASE 这两个术语都好记有余而精确不足，出现较晚的 BASE 硬凑的感觉更明显，它是“Basically Available, Soft state, Eventually consistent（基本可用、软状态、最终一致性）”的首字母缩写。其中的软状态和最终一致性这两种技巧擅于对付存在分区的场合，并因此提高了可用性。
CAP 与 ACID 的关系更复杂一些，也因此引起更多误解。其中一个原因是 ACID 的 C 和 A 字母所代表的概念不同于 CAP 的 C 和 A。还有一个原因是选择可用性只部分地影响 ACID 约束。
进一步看[分区]之后
用一下这张图引用[3]，在状态 S 的时候是非分区状态，而分区模式则演化出来了 S1，S2，那么问题来了，分区恢复之后，状态究竟是多少呢？有几种解决方案。
注意，能支持此类处理的场景是有限的。
riak_dt [4] 就是这样一种保障最终一致性实现的数据结构。它分为基于状态的 CRDTs（State-based CRDTs）和基于操作的 CRDTs（Operation-based CRDTs），基于状态的 CRDTs 是于传播状态的复制，而基于操作的 CRDTs 则是传播操作。[5]
State-based CRDTs 被称为复制收敛的数据类型(CvRDTs)，不同于 CmRDTs，CvRDTs 会将其所有本地状态发送到其他副本。CvRDTs 具有以下本地接口：
查询-读取副本的状态，没有副作用
更新-根据某些限制向复制状态写入
合并-将本地状态与远程副本状态合并
合并函数必须是可交换的、结合的和幂等的。它为任意一对复制状态提供了一个连接，因此所有状态集都形成了连接状态。更新函数必须按照与半格相同的偏序规则单调地增加内部状态。
Operation-based CRDTs 被称为可交换多副本数据类型(CmRDTs)，操作分为两个阶段：prepare 和 effect，prepare 在本地节点上执行。它着眼于操作和（可选）当前状态，并产生一个代表操作的消息，然后分发给所有的其他节点。
分区恢复策略：回放合并在分区恢复过程中，设计师必须解决两个问题：
分区两侧的状态最终必须保持一致，
并且必须补偿分区期间产生的错误。
如上图所示，对于分区恢复的状态 S* 可以通过未分区时的状态 S 为起点，然后按顺序[回放]相应的变化事件[以特定方式推进分区两侧的一系列操作，并在过程中一直保持一致的状态。]。Bayou [5] 就是这个实现机制，它会回滚数据库到正确的时刻并按无歧义的、确定性的顺序重新执行所有的操作，最终使所有的节点达到相同的状态。
对于有冲突的情况，比如版本管理软件 cvs，存在人工介入、消除冲突的处理策略。
有限制处理[3] 提的自动柜员机补偿问题，比较形象说明了这个问题。此问题本质上是可用性和一致性的折衷处理。
以自动柜员机（ATM）的设计来说，强一致性看似符合逻辑的选择，但实际情况也可能有保障部分业务可用的降级处理。因此，讨论如何补偿分区期间被破坏的不变性约束，ATM 的设计很适合作为例子。
ATM 的基本操作是存款、取款、查看余额。关键的不变性约束是余额应大于或等于零。因为只有取款操作会触犯这项不变性约束，也就只有取款操作将受到特别对待，其他两种操作随时都可以执行。
ATM 系统设计师可以选择在分区期间禁止取款操作，因为在那段时间里没办法知道真实的余额，当然这样会损害可用性。现代 ATM 的做法做了一些折中，在 stand-in 模式下（即分区模式），ATM 限制净取款额不得高于 k，比如 k 为 $200。低于限额的时候，取款完全正常；当超过限额的时候，系统拒绝取款操作。这样，ATM 成功将可用性限制在一个合理的水平上，既允许取款操作，又限制了风险。
分区结束的时候，必须有一些措施来恢复一致性和补偿分区期间系统所造成的错误。状态的恢复比较简单，因为操作都是符合交换率的，补偿就要分几种情况去考虑。最后的余额低于零违反了不变性约束。由于 ATM 已经把钱吐出去了，错误成了外部事实。银行的补偿办法是收取透支费并指望顾客偿还。因为风险已经受到限制，问题并不严重。还有一种情况是分区期间的某一刻余额已经小于零（但 ATM 不知道），此时一笔存款重新将余额变为正的。银行可以追溯产生透支费，也可以因为顾客已经缴付而忽略该违反情况。
总而言之，因为通信延迟的存在，银行系统不依靠一致性来保证正确性，而更多地依靠审计和补偿。“空头支票诈骗”也是类似的例子，顾客赶在多家分行对账之前分别取出钱来然后逃跑。透支的错误过后才会被发现，对错误的补偿也许体现为法律行动的形式。
此前，国内某行 IBM 大型机宕机，系统没有第一时间切换到热备或者异地容灾上，直接影响国内某行的信用卡支付相关业务，直到 4 小时之后才恢复服务。有对应的的原因包括日常演练等问题，等更重要的是在[可用性和一致性]之间选择了一致性，4H 之后提供服务，备库仍然主要起数据备份的作用。
有限制处理方案是需要冒险滴，为了保障可用性，无法保障数据 100% 精确，可以折衷提供部分有损服务。比如取款根据信用是不是能限制一定金额，而存款是 OK 的等等。大额对公业务也可以采取具体办法，当然这将在精细化管理服务能力及配套能力上付出更多的IT成本。
超越 CAP？
2011 年 11 月 Twitter 的首席工程师 Nathan Marz 写了一篇文章，描述了他是如何试图打败 CAP 定理的： How to beat the CAP theorem。
作者表示不是要“击败”CAP，而是尝试对数据存储系统进行重新设计，以可控的复杂度来实现 CAP。Marz 认为一个分布式系统面临 CAP 难题的两大问题就是：在数据库中如何使用不断变化的数据，如何使用算法来更新数据库中的数据。
Marz 提出了 2 个基本思路：
1) 数据不存在 update，只存在 append 操作。这样就把对数据的处理由 CRUD 变为 CR；同样的，delete 操作也可以处理为 add 一条新记录：比如友强取消了对山丘的关注，传统关系型数据库是在关系表删除一条记录，而 Marz 也可以新增一条关系为[取消]的记录。
2) 所有的数据的操作就只剩下 Create和Read。把 Read 作为一个 Query 来处理，而一个 Query 就是一个对整个数据集执行一个函数操作。
总结，在有一定时序性，且对实时一致性要求不高的场景下可以选择使用，毕竟在问题解决域多了一把锤子。Query 过程中的跨分区函数仍然是一种合并的变种（Merge）！
OceanBase 的另类之路
既然更新数据涉及到分区问题，那么能不能把更新放到一个服务器呢[脑洞大开]？然后通过强大的软件+硬件能力一起去保障它！同时已经不修改的数据天然具备可扩展性！这是我粗暴理解 OceanBase 的基本设计思想。
OceanBase 的逻辑架构简图
关于 UpdateServer 的性能问题
其实大部分数据库每天的修改次数相当有限，只有少数修改比较频繁的数据库才有每天几亿次的修改次数。另外，数据库平均每次修改涉及的数据量很少，很多时候只有几十个字节到几百个字节。假设数据库每天更新 1 亿次，平均每次需要消耗 100 字节，每天插入 1000 万次，平均每次需要消耗 1000 字节，那么，一天的修改量为：1亿 * 100 + 1000万 * 1000 = 20GB，如果内存数据结构膨胀 2 倍，占用内存只有 40GB。而当前主流的服务器都可以配置 96GB 内存，一些高档的服务器甚至可以配置 192GB、384GB 乃至更多内存。
总 结
CAP 是分布式领域的重要理论，但不代表完全不能有延展的解读和思考。另外[三选二]本身也是有条件成立的，不能简单误读，一切取决于应用场景。如果不加选择按照理论形式无异于刻舟求剑。
欲了解更多有关分布式缓存方面的内容，请阅读《深入分布式缓存:从原理到实践》一书。
参考：
[1] ：http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf
[2] http://www.royans.net/wp/2010/02/14/brewers-cap-theorem-on-distributed-systems/
[3] ：http://www.infoq.com/cn/articles/cap-twelve-years-later-how-the-rules-have-changed/
[4]：https://github.com/basho/riak_dt
[5]：https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
[6] ：http://www.cs.berkeley.edu/~brewer/cs262b/update-conflicts.pdf
相关热文
长按二维码关注我们 ▶▶▶
点击【阅读原文】获取招聘信息或发送简历到 sofa@cloud.alipay.com，期待您的加入！